9/29忙著看棒球，來不及刷當天的難題。


9月的badge還沒拿到。
還好Leetcode每個月有兩次拯救(redeem)的機會，可以回溯完成沒刷到的daily題~

2024/09/29

Leetcode Daily Problem

題目: 432. All O`one Data Structure
難度: 難

題意

設計一個可以儲存字串計數的類別，並能夠回傳計數最小和最大的字串。

實作AllOne類別：
AllOne()：初始化資料結構的物件。
inc(String key)：將字串key的計數加1。如果key不存在於資料結構中，則將其加入並設為計數1。
dec(String key)：將字串key的計數減1。如果key的計數在減少後變為0，則將其從資料結構中移除。保證在減少計數前，key一定存在於資料結構中。
getMaxKey()：回傳計數最大的其中一個字串。如果沒有任何元素存在，則回傳空字串""。
getMinKey()：回傳計數最小的其中一個字串。如果沒有任何元素存在，則回傳空字串""。
要求，每個函數的平均時間複雜度必須為O(1)。

思路

這題想了很久，如果使用std::map<string, int>會根據鍵(string)做排序，而題目要求取出的是值(int)的最大與最小。關鍵是在更新計數器，能否透過計數器的大小分類字串，並且查詢?

設計兩個哈希表。
哈希表1: 字串->計數器的映射，不需要排序鍵。

哈希表2: 計數器->字串集合的映射，需要在插入時根據鍵排序。

inc(String key)``dec(String key): 更新哈希表1的計數器值，並且得知更新前與新的計數器。
透過更新前和新的來更新哈希表2，在鍵為更新前映射的字串集合拔出string，在鍵為新的映射的字串集合插入string。
getMaxKey()``getMinKey(): 選擇適當的哈希表2，能根據鍵排序好。從哈希表的頭或尾找出隨意一個字串回傳即可。若題目要求所有計數器皆為max/min的字串時，也能以O(1)取出。

實作

class AllOne
{
private:
    // String -> count
    unordered_map<string, int> um;
    // Count -> string
    map<int, unordered_set<string>> mp;

public:
    AllOne()
    {
        um = unordered_map<string, int>{};
        mp = map<int, unordered_set<string>>{};
    }

    void inc(string key)
    {
        int prev_count = um[key];
        um[key]++;
        if (prev_count > 0)
        {
            mp[prev_count].erase(key);
            if (mp[prev_count].empty())
                mp.erase(prev_count);
        }
        mp[um[key]].insert(key);
    }

    void dec(string key)
    {
        int prev_count = um[key];
        um[key]--;
        mp[prev_count].erase(key);
        if (mp[prev_count].empty())
            mp.erase(prev_count);
        if (um[key] == 0)
        {
            um.erase(key);
        }
        else
        {
            mp[um[key]].insert(key);
        }
    }

    string getMaxKey()
    {
        if (!mp.empty())
            return *(mp.rbegin()->second.begin());

        return "";
    }

    string getMinKey()
    {
        if (!mp.empty())
            return *(mp.begin()->second.begin());
        return "";
    }
};

結果

Accepted 22 / 22 test cases passed.
Runtime: 96 ms
Memory Usage: 61.4 MB

總結

成功拿下9月連續刷題的獎牌! 是藍綠色的~~

透過9月連續天天刷題挑戰，目前發現的弱點主題有
滾動哈希，線段樹，字首樹
有遇到題目再努力練習~~